home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 051-075 / disk_051 / sq.usq / tr2.c < prev    next >
C/C++ Source or Header  |  1992-05-06  |  13KB  |  467 lines
  1. /* #define DEBUG */
  2. #include <stdio.h>
  3. #include "sqcom.h"
  4. #include "sq.h"
  5. #define ERROR -1
  6. #define TRUE 1
  7. #define FALSE 0
  8.  
  9. /******** Second translation - bytes to variable length bit strings *********/
  10.  
  11.  
  12. /* This translation uses the Huffman algorithm to develop a
  13.  * binary tree representing the decoding information for
  14.  * a variable length bit string code for each input value.
  15.  * Each string's length is in inverse proportion to its
  16.  * frequency of appearance in the incoming data stream.
  17.  * The encoding table is derived from the decoding table.
  18.  *
  19.  * The range of valid values into the Huffman algorithm are
  20.  * the values of a byte stored in an integer plus the special
  21.  * endfile value chosen to be an adjacent value. Overall, 0-SPEOF.
  22.  *
  23.  * The "node" array of structures contains the nodes of the
  24.  * binary tree. The first NUMVALS nodes are the leaves of the
  25.  * tree and represent the values of the data bytes being
  26.  * encoded and the special endfile, SPEOF.
  27.  * The remaining nodes become the internal nodes of the tree.
  28.  *
  29.  * In the original design it was believed that
  30.  * a Huffman code would fit in the same number of
  31.  * bits that will hold the sum of all the counts.
  32.  * That was disproven by a user's file and was a rare but
  33.  * infamous bug. This version attempts to choose among equally
  34.  * weighted subtrees according to their maximum depths to avoid
  35.  * unnecessarily long codes. In case that is not sufficient
  36.  * to guarantee codes <= 16 bits long, we initially scale
  37.  * the counts so the total fits in an unsigned integer, but
  38.  * if codes longer than 16 bits are generated the counts are
  39.  * rescaled to a lower ceiling and code generation is retried.
  40.  */
  41.  
  42. /* Initialize the Huffman translation. This requires reading
  43.  * the input file through any preceding translation functions
  44.  * to get the frequency distribution of the various values.
  45.  */
  46.  
  47. init_huff(ib)          
  48. FILE *ib;
  49. {
  50.     int c, i;
  51.     int btlist[NUMVALS];    /* list of intermediate binary trees */
  52.     int listlen;        /* length of btlist */
  53.     unsigned int *wp;    /* simplifies weight counting */
  54.     unsigned int ceiling;    /* limit for scaling */
  55.  
  56.     /* Initialize tree nodes to no weight, no children */
  57.     init_tree();
  58.  
  59.     /* Build frequency info in tree */
  60.     do {
  61.         c = getcnr(ib);        
  62.         if(c == EOF)
  63.             c = SPEOF;
  64.         if(*(wp = &node[c].weight) !=  MAXCOUNT)
  65.             ++(*wp);
  66.     } while(c != SPEOF);
  67. #ifdef DEBUG
  68.     pcounts();    /* debugging aid */
  69. #endif    
  70.     ceiling = MAXCOUNT;
  71.  
  72.     do {    /* Keep trying to scale and encode */
  73.         if(ceiling != MAXCOUNT)
  74.             printf("*** rescaling ***, ");
  75.         scale(ceiling);
  76.         ceiling /= 2;    /* in case we rescale */
  77. #ifdef DEBUG
  78.         pcounts();    /* debugging aid */
  79. #endif
  80.  
  81.         /* Build list of single node binary trees having
  82.          * leaves for the input values with non-zero counts
  83.          */
  84.         for(i = listlen = 0; i < NUMVALS; ++i)
  85.             if(node[i].weight != 0) {
  86.                 node[i].tdepth = 0;
  87.                 btlist[listlen++] = i;
  88.             }
  89.  
  90.         /* Arrange list of trees into a heap with the entry
  91.          * indexing the node with the least weight at the top.
  92.          */
  93.         heap(btlist, listlen);
  94.  
  95.         /* Convert the list of trees to a single decoding tree */
  96.         bld_tree(btlist, listlen);
  97.  
  98.         /* Initialize the encoding table */
  99.         init_enc();
  100.  
  101.         /* Try to build encoding table.
  102.          * Fail if any code is > 16 bits long.
  103.          */
  104.     } while(buildenc(0, dctreehd) == ERROR);
  105. #ifdef DEBUG
  106.     phuff();    /* debugging aid */
  107. #endif
  108.     /* Initialize encoding variables */
  109.     cbitsrem = 0;    /*force initial read */
  110.     curin = 0;    /*anything but endfile*/
  111. }
  112. /*   */
  113. /* The count of number of occurrances of each input value
  114.  * have already been prevented from exceeding MAXCOUNT.
  115.  * Now we must scale them so that their sum doesn't exceed
  116.  * ceiling and yet no non-zero count can become zero.
  117.  * This scaling prevents errors in the weights of the
  118.  * interior nodes of the Huffman tree and also ensures that
  119.  * the codes will fit in an unsigned integer. Rescaling is
  120.  * used if necessary to limit the code length.
  121.  */
  122.  
  123. scale(ceil)
  124. unsigned int ceil;    /* upper limit on total weight */
  125. {
  126.     int c, ovflw, divisor, i;
  127.     unsigned int w, sum;
  128.     char increased;        /* flag */
  129.  
  130.     do {
  131.         for(i = sum = ovflw = 0; i < NUMVALS; ++i) {
  132.             if(node[i].weight > (ceil - sum))
  133.                 ++ovflw;
  134.             sum += node[i].weight;
  135.         }
  136.  
  137.         divisor = ovflw + 1;
  138.  
  139.         /* Ensure no non-zero values are lost */
  140.         increased = FALSE;
  141.         for(i = 0; i < NUMVALS; ++i) {
  142.             w = node[i].weight;
  143.             if (w < divisor && w > 0) {
  144.                 /* Don't fail to provide a code if it's used at all */
  145.                 node[i].weight = divisor;
  146.                 increased = TRUE;
  147.             }
  148.         }
  149.     } while(increased);
  150.  
  151.     /* Scaling factor choosen, now scale */
  152.     if(divisor > 1)
  153.         for(i = 0; i < NUMVALS; ++i)
  154.             node[i].weight /= divisor;
  155. }
  156. /*   */
  157. /* heap() and adjust() maintain a list of binary trees as a
  158.  * heap with the top indexing the binary tree on the list
  159.  * which has the least weight or, in case of equal weights,
  160.  * least depth in its longest path. The depth part is not
  161.  * strictly necessary, but tends to avoid long codes which
  162.  * might provoke rescaling.
  163.  */
  164.  
  165. heap(list, length)
  166. int list[], length;
  167. {
  168.     int i;
  169.  
  170.     for(i = (length - 2) / 2; i >= 0; --i)
  171.         adjust(list, i, length - 1);
  172. }
  173.  
  174. /* Make a heap from a heap with a new top */
  175.  
  176. adjust(list, top, bottom)
  177. int list[], top, bottom;
  178. {
  179.     int k, temp;
  180.     char cmptrees();
  181.  
  182.     k = 2 * top + 1;    /* left child of top */
  183.     temp = list[top];    /* remember root node of top tree */
  184.     if( k <= bottom) {
  185.         if( k < bottom && cmptrees(list[k], list[k + 1]))
  186.             ++k;
  187.  
  188.         /* k indexes "smaller" child (in heap of trees) of top */
  189.         /* now make top index "smaller" of old top and smallest child */
  190.         if(cmptrees(temp, list[k])) {
  191.             list[top] = list[k];
  192.             list[k] = temp;
  193.             /* Make the changed list a heap */
  194.             adjust(list, k, bottom); /*recursive*/
  195.         }
  196.     }
  197. }
  198.  
  199. /* Compare two trees, if a > b return true, else return false
  200.  * note comparison rules in previous comments.
  201.  */
  202.  
  203. char    /* Boolean */
  204. cmptrees(a, b)
  205. int a, b;    /* root nodes of trees */
  206. {
  207.     if(node[a].weight > node[b].weight)
  208.         return (TRUE);
  209.     if(node[a].weight == node[b].weight)
  210.         if(node[a].tdepth > node[b].tdepth)
  211.             return (TRUE);
  212.     return (FALSE);
  213. }
  214. /*   */
  215. /* HUFFMAN ALGORITHM: develops the single element trees
  216.  * into a single binary tree by forming subtrees rooted in
  217.  * interior nodes having weights equal to the sum of weights of all
  218.  * their descendents and having depth counts indicating the
  219.  * depth of their longest paths.
  220.  *
  221.  * When all trees have been formed into a single tree satisfying
  222.  * the heap property (on weight, with depth as a tie breaker)
  223.  * then the binary code assigned to a leaf (value to be encoded)
  224.  * is then the series of left (0) and right (1)
  225.  * paths leading from the root to the leaf.
  226.  * Note that trees are removed from the heaped list by
  227.  * moving the last element over the top element and
  228.  * reheaping the shorter list.
  229.  */
  230.  
  231. bld_tree(list, len)
  232. int list[];
  233. int len;
  234. {
  235.     int freenode;        /* next free node in tree */
  236.     int lch, rch;        /* temporaries for left, right children */
  237.     struct nd *frnp;    /* free node pointer */
  238.     int i;
  239.     char maxchar();
  240.  
  241.     /* Initialize index to next available (non-leaf) node.
  242.      * Lower numbered nodes correspond to leaves (data values).
  243.      */
  244.     freenode = NUMVALS;
  245.  
  246.     while(len > 1) {
  247.         /* Take from list two btrees with least weight
  248.          * and build an interior node pointing to them.
  249.          * This forms a new tree.
  250.          */
  251.         lch = list[0];    /* This one will be left child */
  252.  
  253.         /* delete top (least) tree from the list of trees */
  254.         list[0] = list[--len];
  255.         adjust(list, 0, len - 1);
  256.  
  257.         /* Take new top (least) tree. Reuse list slot later */
  258.         rch = list[0];    /* This one will be right child */
  259.  
  260.         /* Form new tree from the two least trees using
  261.          * a free node as root. Put the new tree in the list.
  262.          */
  263.         frnp = &node[freenode];    /* address of next free node */
  264.         list[0] = freenode++;    /* put at top for now */
  265.         frnp->lchild = lch;
  266.         frnp->rchild = rch;
  267.         frnp->weight = node[lch].weight + node[rch].weight;
  268.         frnp->tdepth = 1 + maxchar(node[lch].tdepth, node[rch].tdepth);
  269.         /* reheap list  to get least tree at top*/
  270.         adjust(list, 0, len - 1);
  271.     }
  272.     dctreehd = list[0];    /*head of final tree */
  273. }
  274. /*   */
  275. char
  276. maxchar(a, b)
  277. char a, b;
  278. {
  279.     return (a > b ? a : b);
  280. }
  281. /* Initialize all nodes to single element binary trees
  282.  * with zero weight and depth.
  283.  */
  284.  
  285. init_tree()
  286. {
  287.     int i;
  288.  
  289.     for(i = 0; i < NUMNODES; ++i) {
  290.         node[i].weight = 0;
  291.         node[i].tdepth = 0;
  292.         node[i].lchild = NOCHILD;
  293.         node[i].rchild = NOCHILD;
  294.     }
  295. }
  296.  
  297. init_enc()
  298. {
  299.     int i;
  300.  
  301.     /* Initialize encoding table */
  302.     for(i = 0; i < NUMVALS; ++i) {
  303.         codelen[i] = 0;
  304.     }
  305. }
  306. /*   */
  307. /* Recursive routine to walk the indicated subtree and level
  308.  * and maintain the current path code in bstree. When a leaf
  309.  * is found the entire code string and length are put into
  310.  * the encoding table entry for the leaf's data value.
  311.  *
  312.  * Returns ERROR if codes are too long.
  313.  */
  314.  
  315. int        /* returns ERROR or NULL */
  316. buildenc(level, root)
  317. int level;/* level of tree being examined, from zero */
  318. int root; /* root of subtree is also data value if leaf */
  319. {
  320.     int l, r;
  321.  
  322.     l = node[root].lchild;
  323.     r = node[root].rchild;
  324. #ifdef DEBUG
  325.     if (debug) printf("level=%d,root=%d,l=%d,r=%d,tcode=%04x\n",level,root,l,r,tcode);
  326. #endif
  327.     if( l == NOCHILD && r == NOCHILD) {
  328.         /* Leaf. Previous path determines bit string
  329.          * code of length level (bits 0 to level - 1).
  330.          * Ensures unused code bits are zero.
  331.          */
  332.         codelen[root] = level;
  333.         code[root] = tcode & ((unsigned int)(~0) >> ((sizeof(int) * 8) - level));
  334. #ifdef DEBUG
  335.         if (debug) printf("  codelen[%d]=%d,code[%d]=%02x\n",root,codelen[root],root,code[root]);
  336. #endif
  337.         return ((level > 16) ? ERROR : NULL);
  338.     } else {
  339.         if( l != NOCHILD) {
  340.             /* Clear path bit and continue deeper */
  341.             tcode &= ~(1 << level);
  342.             /* NOTE RECURSION */
  343.             if(buildenc(level + 1, l) == ERROR)
  344.                 return (ERROR);
  345.         }
  346.         if(r != NOCHILD) {
  347.             /* Set path bit and continue deeper */
  348.             tcode |= 1 << level;
  349.             /* NOTE RECURSION */
  350.             if(buildenc(level + 1, r) == ERROR)
  351.                 return (ERROR);
  352.         }
  353.     }
  354.     return (NULL);    /* if we got here we're ok so far */
  355. }
  356. /*   */
  357. /* Write out the header of the compressed file */
  358.  
  359. wrt_head(ob, infile)
  360. FILE *ob;
  361. char *infile;    /* input file name (w/ or w/o drive) */
  362. {
  363.     int i, k, l, r;
  364.     int numnodes;        /* nbr of nodes in simplified tree */
  365.  
  366.     putwe(RECOGNIZE, ob);    /* identifies as compressed */
  367.     putwe(crc, ob);        /* unsigned sum of original data */
  368.  
  369.     /* Record the original file name w/o drive */
  370.     if(*(infile + 1) == ':')
  371.         infile += 2;    /* skip drive */
  372.  
  373.     do {
  374.         putce(*infile, ob);
  375.     } while(*(infile++) != '\0');
  376.  
  377.  
  378.     /* Write out a simplified decoding tree. Only the interior
  379.      * nodes are written. When a child is a leaf index
  380.      * (representing a data value) it is recoded as
  381.      * -(index + 1) to distinguish it from interior indexes
  382.      * which are recoded as positive indexes in the new tree.
  383.      * Note that this tree will be empty for an empty file.
  384.      */
  385.  
  386.     numnodes = dctreehd < NUMVALS ? 0 : dctreehd - (NUMVALS -1);
  387.     putwe(numnodes, ob);
  388.  
  389.     for(k = 0, i = dctreehd; k < numnodes; ++k, --i) {
  390.         l = node[i].lchild;
  391.         r = node[i].rchild;
  392.         l = l < NUMVALS ? -(l + 1) : dctreehd - l;
  393.         r = r < NUMVALS ? -(r + 1) : dctreehd - r;
  394.         putwe(l, ob);    /* left child */
  395.         putwe(r, ob);    /* right child */
  396.     }
  397. }
  398. /*   */
  399. /* Get an encoded byte or EOF. Reads from specified stream AS NEEDED.
  400.  *
  401.  * There are two unsynchronized bit-byte relationships here.
  402.  * The input stream bytes are converted to bit strings of
  403.  * various lengths via the static variables named c...
  404.  * These bit strings are concatenated without padding to
  405.  * become the stream of encoded result bytes, which this
  406.  * function returns one at a time. The EOF (end of file) is
  407.  * converted to SPEOF for convenience and encoded like any
  408.  * other input value. True EOF is returned after that.
  409.  *
  410.  * The original gethuff() called a seperate function,
  411.  * getbit(), but that more readable version was too slow.
  412.  */
  413.  
  414. int                /*  Returns byte values except for EOF */
  415. gethuff(ib)
  416. FILE *ib;
  417. {
  418.     unsigned int rbyte;    /* Result byte value */
  419.     char need, take;    /* numbers of bits */
  420.  
  421.     rbyte = 0;
  422.     need = 8;        /* build one byte per call */
  423.  
  424.     /* Loop to build a byte of encoded data
  425.      * Initialization forces read the first time
  426.      */
  427.  
  428. loop:
  429.     if(cbitsrem >= need) {
  430.         /* Current code fullfills our needs */
  431.         if(need == 0)
  432.             return (rbyte & 0xff);
  433.         /* Take what we need */
  434.          rbyte |= ccode << (8 - need);
  435.         /* And leave the rest */
  436.         ccode >>= need;
  437.         cbitsrem -= need;
  438.         return (rbyte & 0xff);
  439.     }
  440.  
  441.     /* We need more than current code */
  442.     if(cbitsrem > 0) {
  443.         /* Take what there is */
  444.         rbyte |= ccode << (8 - need);
  445.         need -= cbitsrem;
  446.     }
  447.     /* No more bits in current code string */
  448.     if(curin == SPEOF) {
  449.         /* The end of file token has been encoded. If
  450.          * result byte has data return it and do EOF next time
  451.          */
  452.         cbitsrem = 0;
  453.  
  454.         return ((need == 8) ? EOF : rbyte & 0xff);
  455.     }
  456.  
  457.     /* Get an input byte */
  458.     if((curin = getcnr(ib)) == EOF)
  459.         curin = SPEOF;    /* convenient for encoding */
  460.  
  461.     /* Get the new byte's code */
  462.     ccode = code[curin];
  463.     cbitsrem = codelen[curin];
  464.  
  465.     goto loop;
  466. }
  467.